package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/21 10:36
 * @description <p>0 和 1 个数相同的子数组</p>
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 题目：输入一个只包含 0 和 1 的数组，请问如何求 0 和 1 的个数相同
 * 的最长连续子数组的长度？例如，在数组[0, 1, 0]中有两个子数组包含相同
 * 个数的 0 和 1，分别是[0, 1]和[1, 0]，它们的长度都是 2，因此输出 2。
 */
public class toOffer2_3_11 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 1};
        System.out.println(findMaxLength(nums));
    }

    /**
     * 因为数组里只有0和1两种数据，那么可以把0全都替换成-1，这样题目就变成了求子数组的值之和为0的最大子数组
     * 如果sum(n) = sum(n-j)，那么从n-j到n的这j个值的和就为0
     *
     * @param nums
     * @return
     */
    public static int findMaxLength(int[] nums) {
        //map里存的数据：k是sum、v是每个sum第一次出现的下标号
        Map<Integer, Integer> map = new HashMap<>();
        //初始化
        map.put(0, -1);

//        //用-1取代nums中的0
//        List<Integer> list = Arrays.stream(nums)
//                .map(o -> o = o == 0 ? -1 : 1)
//                .boxed().collect(Collectors.toList());

        int sum = 0;
        int result = 0;

        for (int i = 0; i < nums.length; i++) {
            // 直接赋值的时候做判断就可以了，不用另外new一个list
            sum += nums[i] == 0 ? -1 : 1;
            if (map.containsKey(sum)){
                result = Math.max(i - map.get(sum), result);
            }else {
                // sum在map中不存在的情况，才添加sum和i。
                // 也就是说不会更新map里的旧数据，只会添加新数据，这个新数据就是sum值和对应sum第一次出现的下标号码
                map.put(sum, i);
            }
        }

        return result;
    }
}
